class Node{
    public int val;
    public Node next;
    public Node(int val){
        this.val=val;
    }
}
public class MyLinKedList {
    public Node head;
    //打印链表
    public void listshow(){
        if(this.head==null){
            System.out.println("链表为空，无法打印！");
            return;
        }
        Node cur=this.head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }


    //链表长度
    public int listsize(){
        int count=0;
        Node cur=this.head;
        while(cur!=null) {
            count++;
            cur=cur.next;
        }
        return count;
    }

    //查找链表种是否有key节点
    public boolean contains(int key){
        if(this.head==null){
            System.out.println("链表为空，无法查找！");
            return false;
        }
        Node cur=this.head;
        while(cur!=null){
            if(cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }

    //头插
    public void addFirst(int data){
        Node Data=new Node(data);
        if(this.head==null){
            this.head=Data;
            return ;
        }
        Data.next=this.head;
        this.head=Data;
    }

    //尾插
    public void addList(int data){
        Node Data=new Node(data);
        if(this.head==null){
            this.head=Data;
            return ;
        }
        Node cur=this.head;
        while(cur.next!=null){
            cur=cur.next;
        }
        cur.next=Data;
    }

    //插入位置的前一个节点
    public Node searchPrev(int index){
        Node cur=this.head;
        int count=0;
        while(count<index-1){
            cur=cur.next;
            count++;
        }
        return cur;
    }

    //在指定位置插入
    public void addIndex(int index,int data){

        if(index<0||index>this.listsize()){
            System.out.println("位置不合法，无法插入！");
            return ;
        }
        if(index==this.listsize()){
            addList(data);
            return ;
        }
        if(index==0){
            addFirst(data);
            return ;
        }
        Node Data=new Node(data);
        Node cur=this.searchPrev(index);
        Data.next=cur.next;
        cur.next=Data;
    }

    //查找key节点后返回节点
    public Node searchPrevNode(int key){
        Node cur=this.head;
        if(this.head.val==key){
            return this.head;
        }
        while(cur.next!=null){
            if(cur.next.val==key){
                return cur;
            }
            cur=cur.next;
        }
        return null;
    }

    //删除链表中第一个出现key的节点
    public void remove(int key){
        if(this.head==null){
            System.out.println("链表为空，无法删除！");
            return ;
        }
        if(this.head.val==key){
            this.head=this.head.next;
            return;
        }
        Node cur=searchPrevNode(key);
        if(cur==null){
            System.out.println("没有该节点，无法删除！");
            return ;
        }
        cur.next=cur.next.next;
    }

    //删除链表中所有的key节点
    public void removeAllKey(int key){
        Node cur=this.head.next;
        Node prev=this.head;
        while(cur!=null){
            if(cur.val==key) {
                prev.next=cur.next;
                cur = cur.next;
            }else{
                prev=cur;
                cur=cur.next;
            }
        }
        if(this.head.val==key){
            this.head=this.head.next;
        }
    }

    //清空释放链表
    public void clear(){
        while(this.head!=null){
            Node cur=this.head.next;
            this.head=null;
            this.head=cur;
        }
    }

    //链表开始入环的第一个节点
    public Node detectCycle(){
        Node fast=this.head;
        Node slow=this.head;
        while(true){
            if(fast==null||fast.next==null){
                return null;
            }
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                break;
            }
        }
        fast=this.head;
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return fast;
    }

    //给定一个链表，判断链表中是否有环
    public boolean hasCycle(){
        Node fast=this.head;
        Node slow=this.head;
        while(fast==null||fast.next==null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }

    //输入两个链表，找出它们的第一个公共结点
    public Node etIntersectionNode(Node headA, Node headB){
        int lena=0;
        int lenb=0;
        Node cura=headA;
        Node curb=headB;
        while(cura!=null){
            cura=cura.next;
            lena++;
        }
        while(curb!=null){
            curb=curb.next;
            lenb++;
        }
        int len=lena-lenb;
        if(len<0) {
            len = lenb - lena;
            cura = headB;
            curb = headA;
        }else{
            cura=headA;
            curb=headB;
        }
        while(len>0){
            cura=cura.next;
            len--;
        }
        while(cura!=curb){
            cura=cura.next;
            curb=curb.next;
        }
        return cura;
    }


    //链表的回文结构
    public boolean chkPalindrome(){
        Node newhead=reverseList(this.head);
        while(newhead!=null&&this.head!=null){
            if(this.head!=newhead){
                return false;
            }
            newhead=newhead.next;
            this.head=this.head.next;
        }
        return true;
    }
    public Node reverseList(Node head){
        Node cur=this.head;
        Node prev=null;
        while(cur!=null){
            Node curnext=cur.next;
            cur.next=prev;
            prev=cur;
            cur=curnext;
        }
        return prev;
    }



    //删除链表重复节点
    public Node deleteDuplication(){
        Node newhead=new Node(-1);
        Node cur=this.head;
        Node prev=newhead;
        newhead.next=this.head;
        while(cur!=null&&cur.next!=null){
            if(cur.val==cur.next.val) {
                int tmp = cur.val;
                while (cur != null && tmp == cur.val ) {
                    cur = cur.next;
                }
                prev.next = cur;
            }else{
                prev=cur;
                cur=cur.next;
            }
        }
        return newhead.next;
    }



    //链表分割
    public Node partition(int x){
        Node bs=null;
        Node be=null;
        Node as=null;
        Node ae=null;
        Node cur=this.head;
        while(cur!=null){
            if(cur.val>=x) {
                if (as == null) {
                    as = cur;
                    ae = cur;
                } else {
                    ae.next = cur;
                }
                cur = cur.next;
            }else{
                if(bs==null){
                    bs=cur;
                    be=cur;
                }else{
                    be.next=cur;
                }
                cur=cur.next;
            }
        }
        if(bs==null){
            ae.next=null;
            return as;
        }
        if(as==null){
            be.next=null;
            return bs;
        }
        be.next=as;
        ae.next=null;
        return bs;
    }
}
